package exercise02;

// 将 x 减到 0 的最小操作数
// 正难则反
// 转化: 和为 sum - x 的最长子数组的长度
// 那么结果就为 len - 子数组长度
public class Day230710 {
    // 暴力解法找出和为 sum - x 的最长子数组的长度
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int target = -x;
        for (int i = 0; i < n; i++) {
            target += nums[i];
        }
        if (target == 0) {
            return n;
        }
        int max = -1;
        // 遍历所有子数组
        for (int left = 0; left < n; left++) {
            int sum = 0;
            for (int right = left; right < n; right++) {
                sum += nums[right];
                if (sum > target) {
                    break;
                } else if (sum == target) {
                    max = Math.max(max, right - left + 1);
                    break;
                }
            }
        }
        return max == -1 ? max : n - max;
    }

    // 使用滑动窗口优化, 找和为 sum - x 的最长子数组的长度
    public int minOperations2(int[] nums, int x) {
        int n = nums.length;
        int target = -x;
        for (int i = 0; i < n; i++) {
            target += nums[i];
        }
        if (target == 0) {
            // target = sum - x
            // target = 0, 则 x = sum
            return n;
        }
        int max = -1;
        int sum = 0;
        int left = 0;
        int right = 0;
        while (right < n) {
            // 进窗口
            sum += nums[right];
            while (sum >= target && left <= right) {
                // 出窗口
                if (sum == target) {
                    // 更新 和为 target - x 的最长子数组长度
                    max = Math.max(max, right - left + 1);
                }
                sum -= nums[left++];
            }
            right++;
        }
        return max == -1 ? max : n - max;
    }


    public int minOperations3(int[] nums, int x) {
        int n = nums.length;
        int target = -x;
        for (int i = 0; i < n; i++) {
            target += nums[i];
        }
        if (target < 0) {
            return -1;
        }
        if (target == 0) {
            return n;
        }
        int max = -1;
        int sum = 0;
        int left = 0;
        int right = 0;
        while (right < n) {
            // 进窗口
            sum += nums[right];
            while (sum > target) {
                // 出窗口
                sum -= nums[left++];
            }
            if (sum == target) {
                max = Math.max(max, right - left + 1);
            }
            right++;
        }
        return max == -1 ? max : n - max;
    }
}
